A service provider (SP) operates a network over which traffic flows to and/or from one or more customers. The traffic flows through the network over a path. For example, a path may comprise a number of segments (or hops), where each segment identifies a link between adjacent network elements in the service provider's network. Traditional systems select paths for traffic using the same set of criteria for all requests (e.g., shortest path optimized for bandwidth). Thus, the paths (in the service providers network) on which traffic is transported tend to not differ from customer to customer. Some service providers offer different classes of service. Such class differentiation does not change the basic criteria for path selection and may only change how the likelihood that packets are dropped in the network.